//
//  最长公共子串.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/5.
//

import UIKit

class GetLCS: NSObject {
    func QA() {
        print(lcs("abcba", "babca"))
    }
    func lcs(_ str1: String, _ str2: String) -> Int {
        if str1.count == 0 || str2.count == 0 {
            return 0
        }
        let array1 = Array(str1)
        let array2 = Array(str2)
        var getMax = 0
        let count1 = array1.count;
        let count2 = array2.count;

        var dp = Array(repeating: Array(repeating: 0, count: count2 + 1), count: count1 + 1)
        for i in 1...count1 {
            for j in 1...count2 {
                if array1[i - 1] == array2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + 1
                } else {
                    dp[i][j] = 0
                }
                getMax = max(getMax, dp[i][j])
            }
        }
        return getMax
    }
}
